# 给定一个二叉树，返回所有从根节点到叶子节点的路径。
#
#  说明: 叶子节点是指没有子节点的节点。
#
#  示例:
#
#  输入:
#
#    1
#  /   \
# 2     3
#  \
#   5
#
# 输出: ["1->2->5", "1->3"]
#
# 解释: 所有根节点到叶子节点的路径为: 1->2->5, 1->3
#  Related Topics 树 深度优先搜索
#  👍 323 👎 0


# leetcode submit region begin(Prohibit modification and deletion)
# Definition for a binary tree node.
from typing import List


class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution:
    def binaryTreePaths(self, root: TreeNode) -> List[str]:

        def dfs(root, path):
            if root:

                if not root.left and not root.right:
                    path += str(root.val)
                    paths.append(path)

                else:
                    path += str(root.val) + "->"
                    dfs(root.left, path)
                    dfs(root.right, path)

        paths = []

        dfs(root, "")
        return paths

    # leetcode submit region end(Prohibit modification and deletion)
